#include<iostream>
#include<stack>

using namespace std;

struct ListNode {
	int value;
	ListNode * next;	
};


// 创建链表
ListNode * createLink( ListNode * pHead, int value ){
	ListNode * node = new ListNode();
	node -> value = value;
	node -> next = nullptr;
	
	// 判断链表是否为空
	if ( pHead == nullptr ){
		pHead = node ;
	}else {
		ListNode * pNode = pHead;
		while ( pNode -> next != nullptr )
			pNode = pNode -> next;
		// cout << pNode -> value << endl;
		pNode -> next = node;
	}
	return pHead;
}

// 删除节点
ListNode * deleteNode( ListNode * pHead, int key){
	ListNode * fast = pHead;
	ListNode * slow = pHead;
	while ( fast != nullptr && fast -> value != key){
		slow = fast;
		fast = fast -> next;
	}

	if ( fast != nullptr ){
		// 删除头结点
		if ( fast == slow ){
			pHead = fast->next;
		}else {
			slow -> next = fast -> next;
		}
		// 释放节点
		delete fast;
	}
	
	//　当删除头结点时，需要将新的头结点信息返回到回调函数中去
	return pHead;
}

// 从尾到头打印链表
void printListReverse(ListNode * pHead){
	// 使用栈存储，函数递归会引发函数栈溢出
	stack<ListNode *> nodes;
	while ( pHead != nullptr ){
		nodes.push(pHead);
		pHead = pHead -> next;
	}

	ListNode * node = nullptr;
	// 判断栈不为空
	while ( !nodes.empty() ){
		// 出栈
		node = nodes.top();
		cout << node->value << "  ";
		nodes.pop();
	}
	cout << endl;
}


int main(void){
	ListNode * listNode = nullptr;
	listNode = createLink(listNode, 1);
	
	if ( listNode == nullptr )
		cout << "link is empty" << endl;
	else 
		cout << "link not empty" << endl;
	listNode = deleteNode(listNode, 1);
	if ( listNode == nullptr ){
		cout << "linked list is empty" << endl;	
	}
	printListReverse(listNode);
	return 0;
}